The present invention relates to applications involving sampling of objects, such as images, or placement or arrangement of objects, such as sensors, using Low Discrepancy sequences, wherein the use of Low Discrepancy sequences provides improved efficiency. The present invention includes, but is not limited to, methods for sampling images, acquiring image statistics, locating a known object in an image, estimating the motion of objects in successive acquired images, determining placement locations of sensors or other objects, and determining points to be used in a grid/mesh design.
In many applications it is necessary or desired to sample an image to generate sample pixels which characterize the image, rather than using every pixel of the image. These sample pixels can then be used in performing calculations and comparisons associated with the image. Sampling an image may be very advantageous in applications such as pattern matching, image reconstruction, and motion estimation.
In addition, many applications require placement of multiple objects, such as sensors, within a given area. Here it is greatly desirable to optimally place the sensors for best coverage of the area, i.e., to place the sensors in locations which maximize reception. This allows usage of a lesser number of sensors to cover an area, thus reducing cost.
Prior art techniques for sampling an image and for determining placement locations for objects have utilized either a homogeneous sampling, such as grid-based sampling, or have utilized random points or pixels within the placement or image area. However, each of the above prior art techniques operates to select a subset of the total available pixels or total possible locations which does not necessarily best represent or characterize the image or placement objectives.
For example, an improved system and method is desired for characterizing an image with a fewer number of sample pixels. Image characterization is used, for example, in performing correlation based pattern matching. Pattern matching applications often apply an image sampling method to characterize the temple image with a lesser number of sample pixels. Pattern matching applications are used to find instances of the template image or image object in a larger target image. Examples of pattern matching applications include machine vision applications such as process monitoring, feedback control, and laboratory automation; image and video compression; and jitter compensation in video cameras; among others.
Many other operations require and/or desire a more efficient characterization of images. Examples include methods of acquiring image statistics, such as mean gray-level value or standard deviation of gray-levels, methods for locating a known object in an image, methods for estimating the motion of objects in successive acquired images, and methods for color matching, among others. Therefore, an improved system and method is desired for characterizing an image. More particularly, an improved system and method is desired for characterizing or selecting samples or pixels from a template image which best represent the template image with the fewest samples possible.
As discussed above, in many applications it is desired to determine the optimal placement locations for sensors within a given area. For example, a CCD (charge coupled device) sensor in a camera comprises an array of light sensitive electronic capacitors (CCD sensor elements) that are typically placed in a grid based pattern. If fewer CCD sensors elements could be used, the cost of the CCD sensor would be lessened. Placement of CCD sensor elements according to a uniform grid or random placement procedure may not provide the optimal locations for the sensors. Therefore an improved method is desired for determining the placement locations for CCD sensor elements. Other applications where the optimal placement of sensors is desired include the placement of temperature sensors and microphones in a planar array, as well as placement of transmitters/receivers (sensors) for radar, sonar, topography, and magnetic resonance imaging applications.
Meshes are used in many engineering applications including mechanical, structural, and design applications. Prior art methods typically use a grid based mesh, wherein the vertices of the mesh are placed according to a grid pattern. If a fewer number of vertices is used, while achieving substantially the same results, computer memory, time, and other resources are reduced. Therefore an improved method for determining mesh vertices is desired.
Therefore, improved systems and methods are desired for optimally sampling objects, such as pixels in an image; for optimally placing or arranging objects, such as sensors; and for optionally determining locations of vertices in a grid or mesh design.
The present invention comprises a system and method for improved image characterization, object placement, and mesh design utilizing Low Discrepancy sequences. The present invention may be applied specifically to methods of image characterization, pattern matching, acquiring image statistics, object location, image reconstruction, motion estimation, object placement, sensor placement, and mesh design, among others. While these applications are discussed specifically and in detail, they are not intended to limit the use of Low Discrepancy sequences in other applications.
In a first embodiment, the present invention comprises a system and method for performing image characterization using Low Discrepancy sequences. The image characterization is preferably performed in a computer system. The image is received by and/or stored in the computer system and comprises a first plurality of pixels. The system and method comprises sampling the image using a Low Discrepancy sequence, also referred to as a quasi-random sequence, to determine a plurality of sample pixels in the image which characterize the image. The Low Discrepancy sequence is designed to produce sample points which maximally avoid one another, i.e., the distance between any two sample points is maximized. Also, the Low Discrepancy sequence sampling results in fewer points and provides a better characterization of the image than a random sequence sampling or a uniform sampling. Examples of the Low Discrepancy sequence include Halton, Sobol, Faure, and Niederreiter sequences.
Pattern matching is one embodiment in which image characterization using Low Discrepancy sequences may provide a significant increase in efficiency. In a pattern matching application, a template image is received and/or stored in the computer system and comprises a first plurality of pixels. According to one pattern matching embodiment, the system and method first comprises sampling the template image using a Low Discrepancy sequence, as described above. The sampling or characterization of the template image is preferably performed off-line prior to receipt of a target image. Thus the sampling or characterization of the template image is preferably not constrained by real time requirements. After the template image is sampled or characterized, the target image is preferably acquired by the computer system, through a camera or any other image capture method. The method then performs pattern matching using the sample pixels of the template image and the target image to determine zero or more locations of the template image in the target image.
Image characterization using Low Discrepancy sequences may also be used in other applications, such as acquiring image statistics, locating a known object in an image, estimating motion vectors indicating movement of objects in successive images, image reconstruction, image compression, and color matching, among others.
In a second embodiment, the present invention comprises a system and method for optimally placing sensors in a 2D array. In this embodiment, a computer system generates a Low Discrepancy sequence for the desired placement application. The computer system then selects locations for the optimal placement of sensors using the generated Low Discrepancy sequence.
In one embodiment of the present invention, a placement method for CCD sensor elements using a Low Discrepancy sequence may enable a CCD sensor to receive substantially similar sensory information (as that from a grid based array of CCD sensor elements) while reducing the number of CCD sensor elements required. In this embodiment, the area of the CCD sensor panel (the area in which the CCD sensor elements will be placed) and the number of desired CCD sensor elements may first be received by the computer system. This information may either be calculated by the computer or entered by the user, or obtained in any other manner. The computer then generates a Low Discrepancy sequence based on this information to determine the desired CCD sensor element locations on the CCD sensor panel. The generated locations represent the optimal locations for the desired number of CCD sensor elements. The CCD sensor is then constructed, wherein the sensor elements are placed at the locations indicated by the Low discrepancy sequence. The CCD sensor may be constructed by a user or by a machine, e.g., robotics.
The system and method of the present invention may be used for optimally placing other objects or sensors within a 2D or 3D array, such as placement of temperature sensors and microphones in a planar array, as well as placement of transmitters/receivers (sensors) for radar, sonar, topography and magnetic imaging applications, among others.
In a third embodiment, the system and method of the present invention may be used to create meshes using Low Discrepancy sequences. Meshes are used by many engineering applications including mechanical, structural, and design applications. The present invention can be used to optimally create the mesh design, thus achieving improved results and/or improved efficiency.